Modern computer graphics systems and methods include a variety of techniques designed to render high-quality images for use in a wide variety of applications, including video games, flight and other simulation, motion pictures, and many other applications. For example, for animation studios, ray tracing and global illumination techniques now play an integral role in motion picture production and special effects.
Many techniques focus on tracing the path an imaginary ray of light travels as it moves from a light source though a scene. In “ray casting,” for each pixel in a scene, a graphics system traces an imaginary ray from a selected observation point into the scene, to a selected light source, updating pixel color, shading and other factors, based on whether the ray intersects with an object in the scene on its way to the light source. In this way, the graphics system can quickly determine whether an object in a scene is visible to the observation point (visibility), and whether other objects in the scene block light coming from a light source from falling on the object (direct shadows). As such, the graphics system can render a three-dimensional scene into a two-dimensional image suitable for a computer screen, for example. As used herein, “ray casting” means tracing a ray for visibility and direct shadow computations.
In “ray tracing,” particularly Whitted-style ray tracing, when a tracing ray intersects an object in a scene, the graphics system generates one or more of three additional types of rays, “secondary rays,” whose origin is the intersection point of the tracing ray and the object: reflection rays, refraction rays and shadow rays. “Reflection” rays travel from the intersection point in the direction of the mirror reflection path of the original ray. If a reflected ray intersects with another object, that reflected object affects the pixel representing the intersection point, by showing a mirror image of the reflected object on the first object.
If the original tracing ray intersects a transparent object, “refraction” rays travel from the intersection point in the direction of the refraction path of the original ray, and can travel through the object. If a refraction ray intersects with another object, the graphics system updates the pixel representing the intersection point accordingly. If the object faces a light source, “shadow” rays trace a direct-line path from the intersection point to the light source. If a shadow ray intersects an opaque object, the opaque object blocks the light coming from the light source to the intersection point, and the graphics system updates the pixel representing the intersection point accordingly.
In addition to Whitted-style secondary rays, typical graphics systems can also perform a number of other scene manipulations to enhance the photorealism of the depicted scene. For example, “global illumination” (a general term for techniques that add indirect lighting considerations to a scene) adds additional realism to a scene by improving the realism of scene lighting. Because global illumination techniques are frequently resource-intensive, some typical graphics systems use ambient occlusion to simulate global illumination. Generally, “ambient occlusion” casts multiple rays from primary and secondary intersection points, computing coverage ratios based on the number of sample rays that intersect with other objects and surfaces.
Ambient occlusion and ray tracing's secondary rays add detail not available in ray casting, which results in more photorealistic images. However, the additional rays also require additional computation and storage resources. Such additional computation and storage requirements have often made interactive ray tracing impractical or impossible. But recent advances in software techniques have renewed interest in ray tracing images in interactive time frames.
One common approach is to use hierarchical groups or “packets” of rays, which can be tested against an acceleration structure in order to discard a subset of geometry from consideration, such as, for example, when that subset does not reach the observation point. Generally, an acceleration structure is a data structure used to hold information about scene geometry, which can be used to evaluate whether a particular ray path intersects an object in the scene, among other things. Example acceleration structures include the uniform grid, binary tree, KD tree, octree, and bounded-volume hierarchy. Using hierarchical packets of rays and traversing the packets through an acceleration structure often greatly reduces the required number of operations while maintaining acceptable accuracy.
Modern graphics systems, however, typically focus on traversing packets of primary rays and shadow rays (that is, ray casting rays) through accelerations structures, as rays in primary and shadow ray packets share a common origin and have a high degree of directional coherence. But ray tracing's secondary rays, and ambient occlusion rays, for example, typically do not share a common origin, and do not have a high degree of directional coherence. As such, processing secondary rays, even with acceleration structures, is more complicated and computationally intensive than processing typical primary or shadow rays.
Moreover, typical graphics systems use a recursive solution to process ray tracing and global illumination packets, typically a single ray at a time, which resolves shaded colors for secondary rays before the primary color can be returned. For example, FIG. 2 illustrates an example of recursive Whitted-style ray tracing (this disclosure describes FIG. 1 below). As shown, in recursive Whitted-style ray tracing, a “hit” (intersection with a primary ray and an object in the scene) at one level of the process, causes a call to a function that invokes the process at a lower level to process the secondary rays originating at the intersection. Thus, one skilled in the art will understand that, in the common recursive approach shown, processing the secondary rays delays calculation of the primary ray's hit color until all of the secondary rays have been processed.
This recursion presents problems for multi-core processors such as the Cell™, Broadband Engine™, and certain special processing units, such as graphical processing units (GPUs), for example. Specifically, certain such processors restrict local memory, which limits the space available for stack-based function invocation, making performance-prohibitive the complex recursion required in typical algorithms.
Additionally, even where stack-based operations are unlimited, tracing a single ray does not share the cost of memory access latency across a packet of rays. Nor does single-ray processing benefit from other latency solutions such as pipelining, for example. As such, conventional Whitted-style ray tracing is often many times slower than simple ray casting, to the point where conventional ray tracing techniques cannot practically be performed interactively or otherwise in real-time.